#include "Graph.h"
#include "stdio.h"
using namespace std;

// static struct timeval tag;
// static double time[3];
namespace BTLU {

Graph::Graph(int n, int *rows, int *cols, int *degrees, int threshold) {
    // 初始化节点映射
    _n = 0;
    for (int i = 0; i < n; i++)
    {
        if (degrees[i] > threshold)
        {
            _key_nodes.emplace_back(i, degrees[i]);
            _g2l.emplace_back(-1);
        }
        else
        {
            _g2l.emplace_back(_n++);
            _l2g.emplace_back(i);
        }
    }
  

    // 初始化Graph的数据结构
    _edges = vector<vector<int>>(n);
    for (int j = 0; j < n; j++)
    {
        for (int i = cols[j]; i < cols[j + 1]; i++)
        {
            if (_g2l[j] != -1 && _g2l[rows[i]] != -1)
            {
                int x = _g2l[rows[i]];
                int y = _g2l[j];
                _edges[x].emplace_back(y);
                _edges[y].emplace_back(x);
            }
        }
    }
}


// 从给定的start节点开始做BFS
// 若图非连通，则只会遍历部分节点集合
// 节点被遍历时，会设置color_map的对应分量，并触发两个回调函数
void Graph::BFS(int start, int *color_map, ExamineNode examine, FinishNode finish, int color) {
    deque<int> q;
    int dist = 0;
    int q_size = 1;
    int finished_size = 0;
    q.push_back(start);
    color_map[start] = color;
    while (!q.empty()) {
        int node = q.front();
        q.pop_front();

        if (examine != NULL)
            examine(node, q);
        for (int neighbor : _edges[node]) {
            if (color_map[neighbor] != color) {
                q.push_back(neighbor);
                color_map[neighbor] = color;
            }
        }
        if (finish != NULL)
            finish(node, dist, q);
        finished_size++;
        if (finished_size == q_size) {
            finished_size = 0;
            q_size = q.size();
            dist++;
        }
    }
}

void Graph::RcmWithDegree(int *perm) {
  vector<int> result;
  int *colors = (int *)calloc(_n, sizeof(int));
  vector<int> starts;
  int color = 1;
  int i;

    // 在每个连通域选择一个初始节点
    for (i = 0; i < _n; i++) {
        if (colors[i] != color) {
            starts.emplace_back(i);
            this->BFS(i, colors, NULL, NULL, color);
        }
    }
  
  color++;

    // printf("starts size = %d\n", starts.size());

    for (i = 0; i < starts.size(); i++)
    {
        // 选择更好的初始节点x
        int r = starts[i];
        int x = starts[i];
        int y = starts[i];
        int eccen_r = 0;
        int eccen_x = 0;
        int *p_eccen = &eccen_r;
        int *p_node = &x;
        FinishNode finish1 = [p_eccen, p_node, this](int node, int level, deque<int> &q) {
            if (level > *p_eccen || _edges[node].size() < _edges[*p_node].size())
                *p_node = node;
            if (level > *p_eccen)
                *p_eccen = level;
        };

    this->BFS(r, colors, NULL, finish1, color++);
    p_eccen = &eccen_x;
    p_node = &y;
    this->BFS(x, colors, NULL, finish1, color++);

        while (eccen_x > eccen_r)
        {
            r = x;
            eccen_r = eccen_x;
            eccen_x = 0;
            x = y;
            this->BFS(x, colors, NULL, finish1, color++);
        }

        // 使用得到的初始节点x进行BFS
        int q_size = 0;
        ExamineNode exm = [&q_size](int node, deque<int> &q) { q_size = q.size(); };
        FinishNode finish2 = [&result, &q_size, this](int node, int level, deque<int> &q) {
            result.push_back(node);
            std::sort(q.begin() + q_size, q.end(), [this](int a, int b) { return _edges[a].size() < _edges[b].size(); });
        };
        // printf("start vertex = %d\n", x);
        this->BFS(x, colors, exm, finish2, color++);
    }

    reverse(result.begin(), result.end());
    for (i = 0; i < result.size(); i++)
        perm[i] = _l2g[result[i]];

    sort(
        _key_nodes.begin(), 
        _key_nodes.end(), 
        [](const pair<int, int>& a, const pair<int, int>& b) {return a.second < b.second;}
    );
    for (auto &key_node : _key_nodes) {
        perm[i++] = key_node.first;
    }

    free(colors);
}

}  // namespace BTLU
